#ifndef PRIM_HEAD
#define PRIM_HEAD
#include<iostream>
#include <iomanip>
#define INFINITY 1e4
using namespace std;

class graph{
public:
    int **adjGraph;//original initiated graph
    int *previous;//previous[i], storing the previous node of i
    int *dist;//dist[i], added 'weight's that costs to reach point i

    graph();
    ~graph();
    void set_edge(int st,int en,int w);
    int first_edge(int i);
    int next_edge(int i,int j);
    void djkstra_process();

};

void show(int**);
void show_djk(int *);




void graph::djkstra_process(){
    previous[0]=0;
    dist[0]=0;

    for(int i=first_edge(0);adjGraph[0][i]>0;i=next_edge(0,i)){
        dist[i]=adjGraph[0][i];
        previous[i]=0;
    }
    for(int i=0;i<6;i++){
        if(dist[i]<INFINITY&&dist[i]>0){
            for(int j=first_edge(i);adjGraph[i][j];j=next_edge(i,j)){
                int tmp=adjGraph[i][j]+dist[i];
                if(dist[j]>tmp){
                    dist[j]=tmp;
                    previous[j]=i;
                }
            }
        }
    }
}



int graph::first_edge(int i){
    for(int j=0;j<6;j++)
    {
        if(adjGraph[i][j]>0)
            return j;
    }
    return -1;
}

int graph::next_edge(int i, int j){
    for(int k=j+1;k<6;k++){
        if(adjGraph[i][k]>0)
            return k;
    }
    return -1;
}

void graph::set_edge(int st, int en, int w){
    adjGraph[st][en]=w;
}

graph::graph(){
    adjGraph=(int **)new int*[6];
    for(int i=0;i<6;i++)
        adjGraph[i]=new int[6];
    dist=new int[6];
    previous=new int[6];

    for(int i=0;i<6;i++){
        dist[i]=INFINITY;
        previous[i]=-1;
        for(int j=0;j<6;j++)
            adjGraph[i][j]=-1;
    }
}

graph::~graph(){
    for(int i=0;i<6;i++)
        delete adjGraph[i];
    delete adjGraph;
    delete dist;
    delete previous;
}

void show(int **matrix){
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            if(matrix[i][j]>0)
                cout<<matrix[i][j]<<"    ";
            else cout<<"*"<<"    ";
        }
        cout<<endl<<endl;
    }
}
void show_djk(int *djk){
    for(int i=0;i<6;i++)
        cout<<djk[i]<<"    ";
}

#endif // PRIM_HEAD

